package algorithms.leetcode;


import java.util.HashSet;
import java.util.Set;

/**
 * Description: 只出现一次的数字
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * 说明：
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * 示例 1:
 * 输入: [2,2,1]
 * 输出: 1
 * 作者：力扣 (LeetCode)
 * 链接： <a href="https://leetcode.cn/leetbook/read/top-interview-questions-easy/x21ib6/">...</a>
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @date: 2022/10/18 16:26
 * @author: Huangjunjie
 * @since JDK 1.8
 */
public class Subject136 {
    public static void main(String[] args) {
        int[] nums = new int[] {4,2,4,1,1};
        System.out.println(solution3(nums));
    }


    @SuppressWarnings("all")
    private static int solution1(int[] nums) {
        for (int num : nums) {
            int conut = 0;
            for (int item : nums) {
                if (num == item) {
                    conut++;
                }
            }
            if (conut == 1) {
                System.out.println(num);
                return num;
            }
        }
        return 0;
    }


    /**
    * Description: 异或运算（推荐）
     * 用0作参照如果有相同的也是返回0
     *
     * 使用异或运算，将所有值进行异或
     * 异或运算，相异为真，相同为假，所以 a^a = 0 ;0^a = a
     *
    * date: 2022/10/18 16:47<br/>
    * @author: Huangjunjie
    * @since JDK 1.8
    */
    @SuppressWarnings("all")

    private static int solution2(int[] nums) {
        int reduce = 0;
        for (int num : nums) {
            reduce =  reduce ^ num;
        }
        return reduce;

    }


    /**
    * Description: <br/> set集合辅助判断（不推荐）
     * 这个应该是最容易想到的，我们遍历数组中的元素，然后在一个个添加到集合Set中，如果添加失败，说明以前添加过，就把他给移除掉。当我们把数组中的所有元素都遍历完的时候，集合Set中只会有一个元素，这个就是我们要求的值。
     *
     * 作者：数据结构和算法
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    * date: 2022/10/18 16:59<br/>
    * @author: Huangjunjie
    * @since JDK 1.8
    */
    private static int solution3(int[] nums) {
        Set<Integer> sets = new HashSet<>();
        for (int num: nums) {
            if(!sets.add(num)){
                sets.remove(num);
            }
        }
        return (int) sets.toArray()[0];
    }
}
